﻿#pragma once
//数据结构的排序方式总结
//分为四大排序方式：
//         插入排序：直接插入排序，希尔排序
//         选择排序：直接选择排序，堆排序
//         交换排序：冒泡排序，快速排序
//         归并排序：归并排序

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>

typedef int HPDataType;       //底层结构就是数组（顺序表）
typedef struct Heap
{
	HPDataType* arr;
	int size;
	int capacity;
}HP;

//比较排序：
//一 插入排序：
//直接插入排序
void InsertSort(int*, int);
//希尔排序
void ShellSort(int*, int);

//二 选择排序：
//直接选择排序
void SelectSort(int*, int);
//堆排序
void HeapSort(int* , int);

//三 交换排序：
//冒泡排序
void BubbleSort(int*, int);
//快速排序        //即可通过递归，也可通过迭代实现（迭代需要借助数据结构，如：栈、队列等）
void QuickSort(int*, int, int);
void QuickSortNonR(int*, int, int);    //迭代----借助堆

//四 归并排序：
void MergeSort(int* arr, int n);        //与快排、堆排序一样，都是nlogn 


//非比较排序：        //即不通过数值比较的方式来完成排序
//计数排序
void CountSort(int* arr, int n);


